/**
 * 有头节点的单链表l={a1,a2,a3....an}
 * 设计空间复杂度为O(1)的算法，将元素转换为
 * [a1,an,a2,an-1,a3,an-2...]
 *
 * 解法：
 * （1）先利用双指针（快慢）找到中间节点
 * （2）反转后半部分的节点
 * （3）用两个头节点指向总的头和后半部分的头
 * （4）移动两个节点
 */

// 结构体定义
typedef struct node
{
    int data;
    struct node *next;
} NODE;

void change_list(NODE *h)
{
    NODE *p, *q, *r, *s;
    p = q = h; // 一起遍历，q走两步，q走一步，当q到达尾节点的时候p到达
    // 要确定对于奇数个元素和偶数个元素都适用
    // 对于偶数个，这个肯定是没有问题的,左侧指针指向的前半部分的最后一个元素
    // 对于奇数个，[1,2,3]
    // while q=1 p=1 q=2
    // while q=3 p=2 完
    // 所以对于奇数个元素，左侧指针最后指向的是中间节点
    while (q->next != nullptr)
    {
        p = p->next;
        q = q->next;
        if (q->next != nullptr)
            q = q->next;
    }


    // 找到中间节点之后，开始反转后半部分
    q = p->next;       // q是要反转的节点头节点
    //p是中间的那个节点
    p->next = nullptr; // 断开前后两半部分 偶数个就是n/2 和 n/2 奇数个就是前半部分多一个，后半部分还是偶数个
    while (q != nullptr)//！！！精髓
    {
        r = q->next;       // 保存q的next
        q->next = p->next; // 将q头插到p里面（头插法的结果和插入顺序相反，达到逆序的目的）
        p->next = q;
        q = r; // q回到原来的next继续反转
    }


    // 反转完毕，设置两个头节点开始插入
    s = h->next;
    q = p->next;
    p->next=nullptr;    
    while (q != nullptr)
    {
        r = q->next;
        q->next = s->next;
        s->next = q;
        s = q->next;
        q = r;
    }
}

// 寻找，反转，合并都是O(n)的复杂度，最后综合为O(n)

#include <iostream>
using namespace std;
int main()
{

    NODE *n4 = new NODE();
    n4->data = 4;
    n4->next = nullptr;

    NODE *n3 = new NODE();
    n3->data = 3;
    n3->next = n4;

    NODE *n2 = new NODE();
    n2->data = 2;
    n2->next = n3;

    NODE *n1 = new NODE();
    n1->data = 1;
    n1->next = n2;

    NODE *head = new NODE();
    head->data = 0;
    head->next = n1;
    NODE *temp = head->next;

    while (temp)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
    change_list(head);
    temp = head->next;
    while (temp)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
}